package com.shixianchen.review_the_day_before.day3;

/**
 * @author ShiXianChen
 * @version V1.0.0
 * @Description TODO
 * @date 2022/11/1 22:28
 */
public class Code06_BursBalloons {
    public static int getMaxScore(int[] arr){
        // 潜规则: L-1 和 R +1 不可以打爆
        int n = arr.length;
        int[] help = new int[n + 2];
        help[0] = 1;
        help[help.length -1] = 1;

        //创建一个缓存列表
        int[][] dp = new int[help.length][help.length];
        //先设置默认值， 防止后期计算
        for (int i = 0; i < help.length; i++) {
            for (int j = 0; j < help.length; j++) {
                dp[i][j] = -1;
            }
        }

        for (int i = 1; i <= n; i++) {
            help[i] = arr[i-1];
        }
        return process(help,1,n,dp);
    }

    private static int process(int[] arr, int L, int R,int[][] dp) {
        //缓存中含有数据
        if (dp[L][R] != -1){
            return dp[L][R];
        }
        //缓存中没有数据
        int ans = 0;
        if (L == R){
            //只剩一个气球
            ans =   arr[L-1] * arr[L] * arr[R+1];
        }else {
            //剩余多个气球的情况
            //最后打包L位置上的气球, 先打爆 L+1 ... R位置上的气球
            int p1 = process(arr,L+1,R,dp) + arr[L-1] * arr[L] * arr[R+1];

            //最后打爆R位置上的气球，先打爆L...R-1 位置上的气球
            int p2 = process(arr,L,R-1,dp)+  arr[L-1]* arr[R] * arr[R+1];

            //获取R获取L 最后打爆的分数
            ans = Math.max(p1,p2);


            //每个位置分别打爆气球
            for (int mid = L+1; mid < R; mid++) {
                //mid 要遵守 不可先打爆，并且是最后打爆
                int burst = process(arr,L,mid-1,dp) + process(arr,mid+1,R,dp) + arr[L-1] * arr[mid]* arr[R+1];
                ans = Math.max(burst,ans);
            }
        }

        dp[L][R] = ans;

        return ans;
    }



    public static void main(String[] args) {
        int[] arr = new int[]{2,3,48,7,99,1,3,77};
        System.out.println("maxScore(arr) = " + getMaxScore(arr));

    }
}
